# Copyright 2024 by UltrafunkAmsterdam (https://github.com/UltrafunkAmsterdam)
# All rights reserved.
# This file is part of the nodriver package.
# and is released under the "GNU AFFERO GENERAL PUBLIC LICENSE".
# Please see the LICENSE.txt file that should have been included as part of this package.


from __future__ import annotations

import asyncio
import logging
import shutil
import types
from typing import (TYPE_CHECKING, Any, Callable, Generator, List, Optional,
                    Set, Tuple, TypeVar, Union)

from .element import Element

if TYPE_CHECKING:
    from .browser import Browser, PathLike

from .. import cdp
from .config import Config

__registered__instances__: Set[Browser] = set()

logger = logging.getLogger(__name__)
T = TypeVar("T")


async def start(
    config: Optional[Config] = None,
    *,
    user_data_dir: Optional[PathLike] = None,
    headless: Optional[bool] = False,
    browser_executable_path: Optional[PathLike] = None,
    browser_args: Optional[List[str]] = None,
    sandbox: Optional[bool] = True,
    lang: Optional[str] = None,
    host: Optional[str] = None,
    port: Optional[int] = None,
    expert: Optional[bool] = None,
    **kwargs: Optional[dict],
) -> Browser:
    """
    helper function to launch a browser. it accepts several keyword parameters.
    conveniently, you can just call it bare (no parameters) to quickly launch an instance
    with best practice defaults.
    note: this should be called ```await start()```


    :param user_data_dir:
    :type user_data_dir: PathLike

    :param headless:
    :type headless: bool

    :param browser_executable_path:
    :type browser_executable_path: PathLike

    :param browser_args: ["--some-chromeparam=somevalue", "some-other-param=someval"]
    :type browser_args: List[str]

    :param sandbox: default True, but when set to False it adds --no-sandbox to the params, also
    when using linux under a root user, it adds False automatically (else chrome won't start
    :type sandbox: bool

    :param lang: language string
    :type lang: str

    :param port: if you connect to an existing debuggable session, you can specify the port here
                 if both host and port are provided, nodriver will not start a local chrome browser!
    :type port: int

    :param host: if you connect to an existing debuggable session, you can specify the host here
                 if both host and port are provided, nodriver will not start a local chrome browser!
    :type host: str

    :param expert:  when set to True, enabled "expert" mode.
                    This conveys, the inclusion of parameters: --disable-web-security ----disable-site-isolation-trials,
                    as well as some scripts and patching useful for debugging (for example, ensuring shadow-root is always in "open" mode)
    :type expert: bool

    :return:
    """
    if not config:
        config = Config(
            user_data_dir,
            headless,
            browser_executable_path,
            browser_args,
            sandbox,
            lang,
            host=host,
            port=port,
            expert=expert,
            **kwargs,
        )
    from .browser import Browser

    return await Browser.create(config)


async def create_from_undetected_chromedriver(
    driver: "undetected_chromedriver.Chrome",
) -> Browser:
    """
    create a nodriver.Browser instance from a running undetected_chromedriver.Chrome instance.
    """
    from .config import Config

    conf = Config()

    host, port = driver.options.debugger_address.split(":")
    conf.host, conf.port = host, int(port)

    # create nodriver Browser instance
    browser = await start(conf)

    browser._process_pid = driver.browser_pid
    # stop chromedriver binary
    driver.service.stop()
    driver.browser_pid = -1
    driver.user_data_dir = None
    return browser


def get_registered_instances():
    return __registered__instances__


def free_port() -> int:
    """
    Determines a free port using sockets.
    """
    import socket

    free_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    free_socket.bind(("127.0.0.1", 0))
    free_socket.listen(5)
    port: int = free_socket.getsockname()[1]
    free_socket.close()
    return port


def deconstruct_browser():
    import time

    for _ in __registered__instances__:
        if not _.stopped:
            _.stop()
        for attempt in range(5):
            try:
                if _.config and not _.config.uses_custom_data_dir:
                    shutil.rmtree(_.config.user_data_dir, ignore_errors=False)
                    print(
                        "successfully removed temp profile %s" % _.config.user_data_dir
                    )
            except FileNotFoundError as e:
                break
            except (PermissionError, OSError) as e:
                if attempt == 4:
                    logger.debug(
                        "problem removing data dir %s\nConsider checking whether it's there and remove it by hand\nerror: %s",
                        _.config.user_data_dir,
                        e,
                    )
                    break
                time.sleep(0.15)
                continue


def filter_recurse_all(
    doc: T, predicate: Callable[[cdp.dom.Node, Element], bool]
) -> List[T]:
    """
    test each child using predicate(child), and return all children for which predicate(child) == True

    :param doc: the cdp.dom.Node object or :py:class:`nodriver.Element`
    :param predicate: a function which takes a node as first parameter and returns a boolean, where True means include
    :return:
    :rtype:
    """
    if not hasattr(doc, "children"):
        raise TypeError("object should have a .children attribute")
    out = []
    if doc and doc.children:
        for child in doc.children:
            if predicate(child):
                # if predicate is True
                out.append(child)
            if child.shadow_roots is not None:
                out.extend(filter_recurse_all(child.shadow_roots[0], predicate))
            out.extend(filter_recurse_all(child, predicate))

    return out


def filter_recurse(doc: T, predicate: Callable[[cdp.dom.Node, Element], bool]) -> T:
    """
    test each child using predicate(child), and return the first child of which predicate(child) == True

    :param doc: the cdp.dom.Node object or :py:class:`nodriver.Element`
    :param predicate: a function which takes a node as first parameter and returns a boolean, where True means include

    """
    if not hasattr(doc, "children"):
        raise TypeError("object should have a .children attribute")

    if doc and doc.children:
        for child in doc.children:
            if predicate(child):
                # if predicate is True
                return child
            if child.shadow_roots:
                shadow_root_result = filter_recurse(child.shadow_roots[0], predicate)
                if shadow_root_result:
                    return shadow_root_result
            result = filter_recurse(child, predicate)
            if result:
                return result


def flatten_frame_tree(
    tree: Union[cdp.page.FrameResourceTree, cdp.page.FrameTree]
) -> Generator[cdp.page.Frame, None, None]:
    yield tree.frame
    if tree.child_frames:
        for child in tree.child_frames:
            yield from flatten_frame_tree(child)


def flatten_frame_tree_resources(
    tree: cdp.page.FrameResourceTree,
) -> Generator[Tuple[cdp.page.Frame, cdp.page.FrameResource], None, None]:
    for res in tree.resources:
        yield tree.frame, res
    if tree.child_frames:
        for child in tree.child_frames:
            yield from flatten_frame_tree(child)


def get_all_param_names(cls):
    comp = cls.mro()
    ret = []
    for c in comp:
        if not hasattr(c, "__annotations__"):
            continue
        for ann in c.__annotations__:
            if ann not in ret:
                ret.append(ann)
    return ret


def circle(
    x, y=None, radius=10, num=10, dir=0
) -> Generator[Tuple[float, float], None, None]:
    """
    a generator will calculate coordinates around a circle.

    :param x: start x position
    :type x: int
    :param y: start y position
    :type y: int
    :param radius: size of the circle
    :type radius: int
    :param num: the amount of points calculated (higher => slower, more cpu, but more detailed)
    :type num: int
    :return:
    :rtype:
    """
    import math

    r = radius
    w = num
    if not y:
        y = x
    a = int(x - r * 2)
    b = int(y - r * 2)
    m = (2 * math.pi) / w
    if dir == 0:
        # regular direction
        ran = 0, w + 1, 1
    else:
        # opposite ?
        ran = w + 1, 0, -1

    for i in range(*ran):
        x = a + r * math.sin(m * i)
        y = b + r * math.cos(m * i)

        yield x, y


def remove_from_tree(tree: cdp.dom.Node, node: cdp.dom.Node) -> cdp.dom.Node:
    if not hasattr(tree, "children"):
        raise TypeError("object should have a .children attribute")

    if tree and tree.children:
        for child in tree.children:
            if child.backend_node_id == node.backend_node_id:
                tree.children.remove(child)
            remove_from_tree(child, node)
    return tree


async def html_from_tree(tree: Union[cdp.dom.Node, Element], target: "nodriver.Tab"):
    if not hasattr(tree, "children"):
        raise TypeError("object should have a .children attribute")
    out = ""
    if tree and tree.children:
        for child in tree.children:
            if isinstance(child, Element):
                out += await child.get_html()
            else:
                out += await target.send(
                    cdp.dom.get_outer_html(backend_node_id=child.backend_node_id)
                )
            out += await html_from_tree(child, target)
    return out


def compare_target_info(
    info1: cdp.target.TargetInfo, info2: cdp.target.TargetInfo
) -> List[Tuple[str, Any, Any]]:
    """
    when logging mode is set to debug, browser object will log when target info
    is changed. To provide more meaningful log messages, this function is called to
    check what has actually changed between the 2 (by simple dict comparison).
    it returns a list of tuples [ ... ( key_which_has_changed, old_value, new_value) ]

    :param info1:
    :type info1:
    :param info2:
    :type info2:
    :return:
    :rtype:
    """
    d1 = info1.__dict__
    d2 = info2.__dict__
    return [(k, v, d2[k]) for (k, v) in d1.items() if d2[k] != v]


def loop():
    loop = asyncio.new_event_loop()
    asyncio.set_event_loop(loop)
    return loop


def cdp_get_module(domain: Union[str, types.ModuleType]):
    """
    get cdp module by given string

    :param domain:
    :type domain:
    :return:
    :rtype:
    """
    import importlib

    if isinstance(domain, types.ModuleType):
        # you get what you ask for
        domain_mod = domain
    else:
        try:
            if domain in ("input",):
                domain = "input_"

            #  fallback if someone passes a str
            domain_mod = getattr(cdp, domain)
            if not domain_mod:
                raise AttributeError
        except AttributeError:
            try:
                domain_mod = importlib.import_module(domain)
            except ModuleNotFoundError:
                raise ModuleNotFoundError(
                    "could not find cdp module from input '%s'" % domain
                )
    return domain_mod


def get_cf_template() -> bytearray:
    """
    this returns a template image (of a checkbox)
    like this: https://ultrafunkamsterdam.github.io/nodriver/_images/template_example.png
    didn't bother the hassle to include image files in my package.
    :return:
    :rtype:
    """
    return bytearray(
        [
            137,
            80,
            78,
            71,
            13,
            10,
            26,
            10,
            0,
            0,
            0,
            13,
            73,
            72,
            68,
            82,
            0,
            0,
            0,
            111,
            0,
            0,
            0,
            73,
            8,
            6,
            0,
            0,
            0,
            51,
            48,
            120,
            75,
            0,
            0,
            0,
            1,
            115,
            82,
            71,
            66,
            0,
            174,
            206,
            28,
            233,
            0,
            0,
            0,
            4,
            103,
            65,
            77,
            65,
            0,
            0,
            177,
            143,
            11,
            252,
            97,
            5,
            0,
            0,
            0,
            9,
            112,
            72,
            89,
            115,
            0,
            0,
            14,
            195,
            0,
            0,
            14,
            195,
            1,
            199,
            111,
            168,
            100,
            0,
            0,
            15,
            213,
            73,
            68,
            65,
            84,
            120,
            94,
            237,
            92,
            105,
            172,
            85,
            213,
            25,
            93,
            119,
            158,
            223,
            192,
            123,
            128,
            96,
            9,
            210,
            2,
            162,
            17,
            67,
            109,
            165,
            145,
            161,
            32,
            134,
            65,
            69,
            193,
            52,
            237,
            175,
            214,
            214,
            214,
            136,
            52,
            105,
            171,
            5,
            106,
            210,
            212,
            90,
            192,
            40,
            21,
            19,
            127,
            52,
            246,
            159,
            65,
            165,
            166,
            150,
            198,
            161,
            168,
            37,
            14,
            209,
            130,
            3,
            56,
            80,
            177,
            104,
            20,
            172,
            32,
            195,
            147,
            65,
            129,
            55,
            220,
            121,
            236,
            90,
            251,
            220,
            253,
            184,
            128,
            76,
            245,
            62,
            251,
            110,
            223,
            89,
            186,
            57,
            231,
            236,
            121,
            127,
            107,
            127,
            223,
            254,
            246,
            57,
            251,
            62,
            79,
            133,
            192,
            151,
            136,
            227,
            27,
            243,
            84,
            175,
            39,
            197,
            73,
            11,
            20,
            25,
            188,
            76,
            103,
            16,
            60,
            5,
            231,
            90,
            9,
            56,
            215,
            19,
            158,
            245,
            143,
            202,
            168,
            66,
            31,
            42,
            42,
            103,
            226,
            148,
            175,
            204,
            16,
            50,
            255,
            86,
            107,
            35,
            114,
            12,
            122,
            98,
            121,
            22,
            241,
            120,
            148,
            90,
            230,
            173,
            223,
            41,
            86,
            225,
            51,
            111,
            242,
            204,
            163,
            92,
            254,
            146,
            210,
            249,
            236,
            115,
            106,
            8,
            150,
            249,
            204,
            114,
            21,
            62,
            43,
            197,
            103,
            98,
            85,
            190,
            218,
            108,
            73,
            55,
            94,
            20,
            153,
            93,
            233,
            65,
            197,
            153,
            177,
            150,
            249,
            95,
            17,
            69,
            143,
            218,
            41,
            33,
            144,
            103,
            164,
            215,
            135,
            130,
            46,
            1,
            95,
            111,
            255,
            84,
            166,
            79,
            200,
            43,
            179,
            227,
            30,
            143,
            135,
            2,
            170,
            152,
            123,
            191,
            223,
            143,
            66,
            161,
            128,
            64,
            160,
            42,
            200,
            186,
            64,
            221,
            183,
            67,
            17,
            244,
            44,
            212,
            14,
            79,
            56,
            85,
            30,
            225,
            104,
            92,
            175,
            96,
            13,
            78,
            150,
            183,
            250,
            92,
            205,
            108,
            133,
            231,
            169,
            222,
            84,
            170,
            21,
            216,
            103,
            155,
            231,
            104,
            189,
            85,
            28,
            159,
            95,
            255,
            244,
            150,
            17,
            201,
            106,
            135,
            114,
            236,
            157,
            156,
            199,
            214,
            99,
            238,
            235,
            77,
            158,
            37,
            204,
            231,
            115,
            230,
            154,
            139,
            190,
            195,
            151,
            98,
            54,
            51,
            153,
            140,
            33,
            213,
            235,
            245,
            34,
            20,
            10,
            85,
            99,
            93,
            124,
            81,
            244,
            41,
            121,
            210,
            192,
            82,
            169,
            132,
            131,
            7,
            15,
            34,
            24,
            12,
            26,
            2,
            115,
            57,
            173,
            37,
            46,
            234,
            129,
            186,
            147,
            39,
            194,
            4,
            173,
            121,
            34,
            78,
            218,
            214,
            209,
            209,
            129,
            65,
            131,
            6,
            153,
            120,
            173,
            127,
            46,
            234,
            131,
            62,
            213,
            60,
            145,
            167,
            181,
            111,
            215,
            174,
            93,
            24,
            49,
            98,
            132,
            209,
            60,
            23,
            245,
            195,
            151,
            66,
            222,
            135,
            31,
            126,
            136,
            81,
            163,
            70,
            245,
            106,
            165,
            139,
            250,
            160,
            238,
            228,
            169,
            58,
            153,
            204,
            218,
            251,
            237,
            219,
            183,
            99,
            244,
            232,
            209,
            134,
            76,
            155,
            230,
            226,
            139,
            163,
            207,
            200,
            147,
            150,
            105,
            189,
            19,
            246,
            236,
            217,
            131,
            161,
            67,
            135,
            154,
            231,
            58,
            55,
            55,
            160,
            81,
            187,
            3,
            117,
            209,
            96,
            112,
            201,
            107,
            96,
            184,
            228,
            53,
            48,
            92,
            242,
            26,
            24,
            46,
            121,
            13,
            12,
            151,
            188,
            6,
            134,
            75,
            94,
            3,
            195,
            37,
            175,
            129,
            225,
            146,
            215,
            192,
            112,
            201,
            107,
            96,
            184,
            228,
            53,
            48,
            92,
            242,
            26,
            24,
            46,
            121,
            13,
            12,
            151,
            188,
            6,
            134,
            75,
            94,
            3,
            163,
            223,
            125,
            207,
            83,
            186,
            190,
            190,
            247,
            244,
            244,
            32,
            30,
            143,
            155,
            51,
            47,
            170,
            43,
            155,
            205,
            226,
            177,
            199,
            30,
            195,
            214,
            173,
            91,
            81,
            44,
            22,
            77,
            80,
            252,
            241,
            31,
            119,
            109,
            155,
            39,
            131,
            202,
            68,
            34,
            17,
            83,
            191,
            14,
            69,
            77,
            158,
            60,
            25,
            243,
            230,
            205,
            235,
            45,
            167,
            179,
            165,
            58,
            237,
            22,
            14,
            135,
            209,
            217,
            217,
            137,
            214,
            214,
            86,
            83,
            38,
            159,
            207,
            155,
            182,
            244,
            65,
            57,
            26,
            141,
            154,
            60,
            246,
            120,
            163,
            202,
            40,
            77,
            117,
            170,
            220,
            169,
            160,
            50,
            182,
            30,
            29,
            198,
            82,
            93,
            221,
            221,
            221,
            72,
            36,
            18,
            166,
            15,
            26,
            151,
            160,
            113,
            171,
            77,
            93,
            21,
            167,
            186,
            219,
            218,
            218,
            204,
            249,
            87,
            139,
            126,
            71,
            158,
            242,
            168,
            131,
            246,
            160,
            146,
            6,
            169,
            65,
            172,
            95,
            191,
            222,
            4,
            9,
            77,
            121,
            20,
            212,
            142,
            173,
            79,
            247,
            138,
            19,
            201,
            167,
            130,
            210,
            37,
            48,
            9,
            89,
            249,
            37,
            184,
            89,
            179,
            102,
            97,
            246,
            236,
            217,
            38,
            62,
            157,
            78,
            155,
            124,
            186,
            183,
            7,
            133,
            107,
            15,
            12,
            235,
            94,
            125,
            18,
            241,
            42,
            47,
            168,
            142,
            88,
            44,
            102,
            136,
            169,
            21,
            238,
            231,
            65,
            99,
            209,
            241,
            71,
            229,
            85,
            61,
            130,
            37,
            74,
            109,
            107,
            194,
            234,
            170,
            186,
            21,
            175,
            124,
            106,
            91,
            227,
            84,
            254,
            90,
            249,
            245,
            59,
            242,
            212,
            217,
            84,
            42,
            101,
            102,
            162,
            58,
            43,
            97,
            171,
            220,
            138,
            21,
            43,
            176,
            119,
            239,
            94,
            172,
            92,
            185,
            210,
            12,
            94,
            65,
            241,
            202,
            99,
            219,
            82,
            80,
            249,
            211,
            193,
            230,
            223,
            183,
            111,
            31,
            150,
            47,
            95,
            142,
            246,
            246,
            118,
            44,
            89,
            178,
            228,
            24,
            65,
            89,
            225,
            218,
            62,
            52,
            53,
            53,
            25,
            1,
            75,
            107,
            53,
            129,
            116,
            21,
            105,
            186,
            74,
            131,
            84,
            159,
            202,
            137,
            212,
            83,
            65,
            132,
            72,
            139,
            68,
            182,
            234,
            179,
            117,
            74,
            187,
            236,
            132,
            210,
            189,
            100,
            168,
            62,
            232,
            94,
            245,
            170,
            156,
            142,
            80,
            218,
            83,
            120,
            194,
            169,
            109,
            204,
            255,
            8,
            26,
            128,
            160,
            78,
            235,
            94,
            131,
            234,
            234,
            234,
            50,
            179,
            82,
            66,
            212,
            192,
            53,
            24,
            165,
            73,
            216,
            34,
            82,
            87,
            13,
            86,
            196,
            156,
            42,
            212,
            66,
            19,
            74,
            144,
            121,
            212,
            100,
            177,
            103,
            75,
            149,
            79,
            132,
            168,
            13,
            213,
            173,
            118,
            85,
            183,
            21,
            166,
            37,
            213,
            106,
            134,
            210,
            149,
            79,
            218,
            122,
            58,
            136,
            20,
            65,
            229,
            212,
            231,
            230,
            230,
            102,
            67,
            160,
            202,
            170,
            110,
            171,
            249,
            154,
            48,
            186,
            87,
            63,
            212,
            150,
            202,
            217,
            254,
            90,
            244,
            59,
            242,
            36,
            60,
            59,
            187,
            37,
            68,
            117,
            90,
            131,
            147,
            57,
            18,
            89,
            10,
            181,
            100,
            88,
            97,
            107,
            128,
            26,
            188,
            205,
            115,
            178,
            160,
            252,
            130,
            213,
            22,
            9,
            77,
            101,
            21,
            175,
            54,
            116,
            149,
            96,
            237,
            228,
            176,
            109,
            40,
            77,
            253,
            80,
            127,
            148,
            166,
            182,
            172,
            192,
            37,
            104,
            105,
            147,
            173,
            251,
            84,
            80,
            29,
            154,
            40,
            202,
            175,
            114,
            42,
            111,
            181,
            53,
            153,
            76,
            154,
            171,
            234,
            87,
            221,
            138,
            215,
            68,
            213,
            85,
            242,
            56,
            222,
            36,
            247,
            59,
            242,
            212,
            65,
            9,
            72,
            130,
            144,
            240,
            172,
            25,
            211,
            189,
            132,
            172,
            171,
            77,
            23,
            116,
            175,
            56,
            43,
            240,
            51,
            129,
            205,
            47,
            168,
            140,
            234,
            18,
            73,
            210,
            30,
            61,
            171,
            77,
            93,
            53,
            243,
            237,
            250,
            35,
            178,
            165,
            97,
            234,
            131,
            44,
            129,
            202,
            136,
            8,
            165,
            233,
            185,
            165,
            165,
            197,
            16,
            114,
            58,
            136,
            44,
            219,
            103,
            213,
            39,
            168,
            46,
            17,
            39,
            147,
            104,
            219,
            213,
            210,
            161,
            250,
            44,
            97,
            106,
            95,
            229,
            106,
            209,
            47,
            205,
            166,
            132,
            34,
            129,
            88,
            178,
            172,
            73,
            84,
            231,
            37,
            100,
            65,
            207,
            74,
            59,
            91,
            88,
            1,
            168,
            172,
            234,
            146,
            160,
            36,
            80,
            171,
            185,
            54,
            216,
            182,
            164,
            37,
            18,
            232,
            225,
            195,
            135,
            205,
            179,
            250,
            166,
            171,
            202,
            171,
            140,
            210,
            118,
            239,
            222,
            109,
            234,
            148,
            73,
            63,
            29,
            84,
            70,
            65,
            26,
            165,
            53,
            92,
            196,
            105,
            210,
            216,
            122,
            165,
            101,
            34,
            77,
            196,
            202,
            211,
            149,
            198,
            9,
            146,
            135,
            218,
            170,
            69,
            191,
            35,
            79,
            3,
            145,
            240,
            36,
            28,
            205,
            54,
            5,
            193,
            14,
            78,
            131,
            173,
            157,
            129,
            122,
            150,
            48,
            116,
            61,
            51,
            148,
            57,
            155,
            29,
            147,
            169,
            80,
            97,
            85,
            161,
            72,
            24,
            1,
            10,
            173,
            84,
            113,
            72,
            49,
            109,
            240,
            63,
            253,
            212,
            142,
            58,
            142,
            92,
            170,
            27,
            107,
            30,
            121,
            24,
            43,
            239,
            89,
            129,
            24,
            133,
            218,
            149,
            162,
            19,
            197,
            252,
            65,
            57,
            45,
            93,
            105,
            44,
            93,
            186,
            28,
            79,
            61,
            179,
            22,
            135,
            59,
            15,
            193,
            87,
            166,
            86,
            51,
            168,
            157,
            138,
            71,
            63,
            209,
            146,
            87,
            232,
            136,
            89,
            63,
            219,
            138,
            115,
            50,
            164,
            82,
            25,
            116,
            31,
            62,
            132,
            27,
            126,
            244,
            125,
            252,
            245,
            137,
            39,
            145,
            47,
            151,
            48,
            168,
            57,
            138,
            157,
            59,
            182,
            99,
            204,
            133,
            23,
            227,
            242,
            89,
            115,
            177,
            225,
            31,
            47,
            171,
            0,
            11,
            115,
            210,
            178,
            79,
            168,
            20,
            144,
            73,
            119,
            155,
            122,
            28,
            218,
            216,
            127,
            231,
            161,
            255,
            64,
            196,
            217,
            153,
            40,
            187,
            47,
            13,
            19,
            57,
            138,
            19,
            105,
            214,
            220,
            89,
            216,
            184,
            90,
            66,
            79,
            14,
            105,
            109,
            25,
            62,
            191,
            242,
            114,
            157,
            36,
            89,
            21,
            105,
            24,
            197,
            144,
            45,
            80,
            219,
            124,
            52,
            209,
            188,
            87,
            123,
            74,
            247,
            202,
            100,
            21,
            179,
            8,
            121,
            43,
            248,
            206,
            149,
            51,
            241,
            192,
            31,
            239,
            199,
            174,
            189,
            135,
            224,
            97,
            191,
            52,
            165,
            58,
            179,
            92,
            239,
            50,
            21,
            108,
            126,
            227,
            29,
            76,
            184,
            116,
            2,
            34,
            9,
            110,
            31,
            216,
            151,
            98,
            58,
            79,
            211,
            80,
            36,
            41,
            25,
            248,
            61,
            212,
            150,
            18,
            219,
            35,
            9,
            185,
            34,
            61,
            99,
            18,
            226,
            173,
            4,
            225,
            39,
            25,
            207,
            191,
            176,
            14,
            115,
            191,
            247,
            93,
            164,
            203,
            108,
            199,
            147,
            198,
            138,
            101,
            191,
            193,
            210,
            223,
            223,
            143,
            151,
            223,
            120,
            19,
            151,
            125,
            125,
            34,
            103,
            108,
            129,
            19,
            43,
            134,
            100,
            182,
            128,
            112,
            68,
            147,
            34,
            205,
            9,
            92,
            132,
            63,
            192,
            45,
            73,
            81,
            189,
            30,
            128,
            224,
            254,
            168,
            122,
            39,
            50,
            29,
            237,
            19,
            105,
            230,
            158,
            105,
            70,
            139,
            249,
            191,
            79,
            19,
            66,
            191,
            128,
            37,
            121,
            173,
            77,
            49,
            92,
            120,
            254,
            88,
            188,
            185,
            121,
            11,
            242,
            228,
            150,
            244,
            192,
            227,
            247,
            225,
            241,
            39,
            158,
            198,
            196,
            111,
            77,
            198,
            176,
            33,
            109,
            40,
            147,
            232,
            124,
            119,
            22,
            193,
            120,
            4,
            94,
            15,
            77,
            99,
            48,
            192,
            73,
            72,
            97,
            251,
            181,
            78,
            123,
            233,
            136,
            5,
            185,
            189,
            40,
            81,
            251,
            130,
            136,
            182,
            36,
            240,
            217,
            254,
            79,
            144,
            229,
            100,
            245,
            249,
            195,
            232,
            62,
            208,
            129,
            131,
            251,
            58,
            48,
            98,
            212,
            24,
            244,
            112,
            171,
            26,
            136,
            134,
            76,
            219,
            250,
            193,
            45,
            167,
            27,
            91,
            211,
            118,
            129,
            125,
            44,
            123,
            208,
            217,
            157,
            33,
            169,
            129,
            129,
            73,
            222,
            241,
            48,
            166,
            173,
            122,
            47,
            24,
            242,
            140,
            178,
            80,
            60,
            230,
            222,
            131,
            22,
            58,
            19,
            83,
            166,
            78,
            195,
            163,
            127,
            249,
            179,
            225,
            92,
            191,
            50,
            12,
            249,
            60,
            216,
            240,
            218,
            70,
            92,
            117,
            245,
            92,
            154,
            180,
            78,
            138,
            184,
            136,
            153,
            87,
            207,
            195,
            152,
            209,
            227,
            25,
            190,
            134,
            123,
            239,
            189,
            27,
            1,
            10,
            153,
            10,
            138,
            7,
            87,
            175,
            198,
            130,
            133,
            11,
            177,
            228,
            87,
            183,
            98,
            228,
            200,
            175,
            226,
            173,
            13,
            27,
            176,
            244,
            183,
            75,
            241,
            204,
            218,
            103,
            176,
            103,
            111,
            7,
            174,
            153,
            59,
            31,
            91,
            183,
            190,
            135,
            89,
            179,
            102,
            224,
            250,
            235,
            127,
            130,
            155,
            127,
            124,
            3,
            158,
            92,
            243,
            40,
            215,
            123,
            173,
            119,
            94,
            28,
            248,
            228,
            0,
            126,
            121,
            235,
            18,
            172,
            90,
            181,
            154,
            207,
            17,
            106,
            125,
            114,
            0,
            146,
            39,
            46,
            164,
            106,
            132,
            72,
            163,
            82,
            29,
            131,
            94,
            243,
            43,
            210,
            12,
            121,
            100,
            74,
            121,
            18,
            77,
            152,
            52,
            101,
            178,
            249,
            221,
            69,
            62,
            157,
            65,
            62,
            151,
            196,
            166,
            87,
            214,
            99,
            203,
            191,
            182,
            226,
            210,
            203,
            38,
            209,
            186,
            166,
            112,
            237,
            85,
            87,
            98,
            241,
            109,
            191,
            198,
            187,
            239,
            111,
            197,
            230,
            215,
            55,
            225,
            239,
            79,
            175,
            197,
            246,
            29,
            29,
            52,
            123,
            244,
            106,
            3,
            65,
            172,
            127,
            233,
            69,
            44,
            92,
            112,
            35,
            118,
            237,
            254,
            55,
            190,
            57,
            241,
            82,
            99,
            158,
            163,
            225,
            4,
            206,
            25,
            60,
            28,
            47,
            189,
            248,
            42,
            198,
            158,
            63,
            14,
            47,
            60,
            255,
            28,
            158,
            250,
            219,
            3,
            152,
            58,
            125,
            18,
            214,
            191,
            242,
            18,
            104,
            105,
            65,
            229,
            69,
            142,
            150,
            245,
            229,
            87,
            223,
            194,
            156,
            217,
            87,
            211,
            169,
            113,
            186,
            52,
            112,
            53,
            143,
            163,
            23,
            77,
            10,
            181,
            4,
            138,
            60,
            57,
            45,
            101,
            179,
            30,
            82,
            201,
            148,
            38,
            2,
            121,
            63,
            246,
            130,
            113,
            124,
            40,
            99,
            203,
            219,
            155,
            185,
            174,
            117,
            227,
            205,
            141,
            175,
            96,
            193,
            205,
            63,
            229,
            122,
            153,
            199,
            190,
            221,
            31,
            35,
            66,
            53,
            153,
            60,
            109,
            26,
            188,
            97,
            160,
            181,
            173,
            29,
            55,
            223,
            180,
            0,
            15,
            62,
            180,
            154,
            107,
            33,
            48,
            100,
            200,
            57,
            184,
            228,
            27,
            19,
            48,
            118,
            204,
            72,
            154,
            203,
            61,
            82,
            39,
            154,
            208,
            36,
            82,
            12,
            177,
            144,
            7,
            93,
            93,
            73,
            106,
            89,
            4,
            93,
            71,
            62,
            53,
            164,
            204,
            156,
            53,
            29,
            239,
            189,
            255,
            46,
            54,
            111,
            121,
            155,
            222,
            103,
            22,
            27,
            55,
            110,
            193,
            148,
            41,
            87,
            224,
            188,
            81,
            195,
            233,
            196,
            1,
            241,
            112,
            108,
            32,
            146,
            87,
            29,
            178,
            200,
            179,
            65,
            177,
            53,
            4,
            114,
            193,
            34,
            105,
            92,
            251,
            184,
            78,
            145,
            54,
            102,
            80,
            25,
            15,
            6,
            181,
            183,
            225,
            182,
            37,
            139,
            240,
            240,
            67,
            15,
            32,
            26,
            10,
            226,
            233,
            167,
            214,
            98,
            220,
            5,
            99,
            48,
            226,
            220,
            102,
            28,
            220,
            127,
            0,
            219,
            62,
            248,
            128,
            218,
            57,
            5,
            35,
            70,
            78,
            192,
            249,
            163,
            199,
            98,
            241,
            226,
            197,
            232,
            73,
            165,
            209,
            195,
            189,
            247,
            158,
            142,
            14,
            227,
            250,
            39,
            18,
            97,
            180,
            15,
            107,
            231,
            134,
            54,
            139,
            8,
            9,
            8,
            144,
            233,
            30,
            58,
            145,
            173,
            195,
            207,
            67,
            231,
            145,
            110,
            198,
            57,
            239,
            80,
            135,
            140,
            24,
            134,
            25,
            51,
            167,
            227,
            217,
            103,
            159,
            197,
            160,
            214,
            176,
            89,
            91,
            127,
            240,
            195,
            27,
            233,
            208,
            105,
            111,
            10,
            244,
            116,
            117,
            14,
            76,
            179,
            249,
            249,
            160,
            247,
            38,
            109,
            35,
            105,
            210,
            188,
            94,
            248,
            233,
            129,
            250,
            252,
            40,
            209,
            243,
            244,
            82,
            106,
            211,
            105,
            58,
            119,
            239,
            216,
            129,
            117,
            235,
            214,
            97,
            48,
            181,
            235,
            219,
            147,
            46,
            54,
            214,
            53,
            95,
            40,
            99,
            206,
            149,
            115,
            177,
            241,
            181,
            13,
            216,
            187,
            123,
            11,
            182,
            125,
            244,
            17,
            118,
            238,
            222,
            135,
            123,
            86,
            46,
            227,
            6,
            222,
            121,
            249,
            160,
            109,
            79,
            79,
            234,
            8,
            178,
            169,
            46,
            70,
            112,
            207,
            152,
            163,
            23,
            205,
            186,
            233,
            11,
            161,
            76,
            15,
            53,
            18,
            137,
            34,
            17,
            11,
            161,
            155,
            251,
            188,
            100,
            247,
            17,
            76,
            159,
            121,
            57,
            94,
            167,
            249,
            253,
            231,
            150,
            237,
            40,
            208,
            124,
            94,
            112,
            209,
            197,
            200,
            208,
            142,
            42,
            125,
            112,
            83,
            235,
            0,
            35,
            207,
            254,
            89,
            140,
            94,
            232,
            185,
            186,
            23,
            115,
            34,
            28,
            103,
            197,
            94,
            233,
            222,
            123,
            189,
            220,
            134,
            112,
            11,
            33,
            215,
            92,
            113,
            225,
            144,
            31,
            23,
            141,
            27,
            131,
            219,
            111,
            191,
            3,
            227,
            199,
            143,
            71,
            144,
            142,
            96,
            62,
            93,
            196,
            180,
            25,
            115,
            240,
            206,
            187,
            31,
            224,
            53,
            174,
            131,
            93,
            157,
            122,
            43,
            194,
            253,
            106,
            69,
            175,
            209,
            128,
            116,
            26,
            104,
            31,
            50,
            148,
            10,
            236,
            231,
            122,
            21,
            64,
            56,
            22,
            101,
            90,
            217,
            188,
            124,
            136,
            132,
            194,
            200,
            113,
            31,
            158,
            229,
            162,
            38,
            7,
            169,
            144,
            77,
            35,
            17,
            15,
            32,
            222,
            148,
            192,
            132,
            75,
            46,
            97,
            185,
            54,
            220,
            121,
            231,
            114,
            58,
            69,
            243,
            16,
            142,
            114,
            25,
            14,
            251,
            208,
            74,
            79,
            181,
            152,
            45,
            245,
            63,
            242,
            244,
            22,
            65,
            51,
            84,
            111,
            26,
            244,
            246,
            67,
            139,
            186,
            246,
            113,
            138,
            147,
            240,
            156,
            61,
            216,
            81,
            216,
            56,
            43,
            244,
            211,
            130,
            44,
            85,
            138,
            202,
            203,
            161,
            87,
            55,
            228,
            34,
            48,
            24,
            244,
            163,
            204,
            122,
            60,
            85,
            251,
            105,
            182,
            15,
            12,
            218,
            11,
            22,
            74,
            116,
            247,
            131,
            206,
            27,
            159,
            88,
            52,
            136,
            43,
            102,
            76,
            167,
            66,
            134,
            113,
            237,
            252,
            249,
            244,
            48,
            203,
            52,
            117,
            62,
            106,
            132,
            23,
            143,
            172,
            121,
            18,
            203,
            110,
            191,
            13,
            151,
            79,
            157,
            136,
            120,
            75,
            59,
            166,
            95,
            49,
            7,
            111,
            109,
            218,
            132,
            128,
            234,
            97,
            217,
            116,
            46,
            207,
            171,
            49,
            196,
            200,
            113,
            15,
            87,
            97,
            3,
            62,
            206,
            28,
            110,
            219,
            104,
            166,
            61,
            224,
            252,
            224,
            77,
            17,
            97,
            238,
            13,
            75,
            188,
            134,
            66,
            81,
            76,
            157,
            50,
            9,
            219,
            182,
            109,
            195,
            117,
            215,
            205,
            71,
            50,
            165,
            137,
            224,
            188,
            113,
            241,
            107,
            111,
            203,
            206,
            159,
            225,
            168,
            207,
            12,
            170,
            78,
            139,
            190,
            125,
            133,
            36,
            156,
            205,
            39,
            33,
            13,
            82,
            229,
            53,
            43,
            101,
            106,
            68,
            162,
            234,
            90,
            180,
            104,
            145,
            41,
            123,
            223,
            125,
            247,
            153,
            244,
            94,
            175,
            240,
            108,
            96,
            154,
            118,
            132,
            167,
            139,
            30,
            111,
            185,
            229,
            22,
            243,
            130,
            248,
            15,
            247,
            255,
            209,
            137,
            239,
            93,
            252,
            156,
            124,
            210,
            74,
            253,
            81,
            27,
            123,
            239,
            167,
            38,
            114,
            99,
            134,
            189,
            159,
            236,
            195,
            87,
            134,
            15,
            67,
            142,
            107,
            143,
            159,
            166,
            181,
            72,
            247,
            93,
            125,
            207,
            28,
            58,
            140,
            54,
            142,
            53,
            203,
            177,
            118,
            39,
            211,
            24,
            28,
            119,
            190,
            52,
            116,
            101,
            104,
            34,
            185,
            209,
            14,
            86,
            82,
            240,
            208,
            193,
            241,
            114,
            111,
            151,
            77,
            82,
            235,
            3,
            113,
            238,
            5,
            203,
            72,
            68,
            41,
            43,
            95,
            25,
            153,
            114,
            158,
            158,
            101,
            6,
            137,
            8,
            101,
            193,
            73,
            182,
            230,
            241,
            231,
            240,
            226,
            250,
            55,
            176,
            236,
            142,
            187,
            232,
            149,
            134,
            181,
            205,
            67,
            129,
            147,
            32,
            70,
            239,
            181,
            223,
            105,
            158,
            32,
            194,
            36,
            80,
            105,
            156,
            136,
            19,
            137,
            86,
            187,
            236,
            132,
            208,
            179,
            210,
            206,
            10,
            226,
            91,
            234,
            196,
            97,
            151,
            88,
            86,
            175,
            157,
            204,
            91,
            156,
            128,
            62,
            237,
            232,
            107,
            1,
            55,
            211,
            36,
            200,
            9,
            186,
            87,
            91,
            12,
            186,
            86,
            77,
            110,
            65,
            175,
            233,
            216,
            246,
            176,
            225,
            231,
            82,
            200,
            210,
            142,
            0,
            124,
            145,
            176,
            89,
            23,
            225,
            15,
            145,
            56,
            58,
            35,
            208,
            251,
            75,
            142,
            35,
            20,
            97,
            222,
            10,
            242,
            153,
            44,
            107,
            161,
            153,
            52,
            106,
            239,
            135,
            55,
            24,
            97,
            92,
            1,
            225,
            68,
            156,
            253,
            40,
            208,
            137,
            241,
            114,
            253,
            203,
            114,
            93,
            205,
            115,
            158,
            84,
            208,
            28,
            137,
            179,
            29,
            224,
            227,
            157,
            29,
            88,
            113,
            215,
            221,
            184,
            245,
            23,
            63,
            231,
            90,
            72,
            23,
            150,
            197,
            203,
            172,
            183,
            72,
            21,
            45,
            146,
            100,
            167,
            71,
            253,
            8,
            246,
            43,
            130,
            213,
            94,
            251,
            149,
            65,
            247,
            150,
            76,
            155,
            46,
            232,
            94,
            113,
            34,
            179,
            168,
            5,
            230,
            52,
            16,
            119,
            218,
            6,
            40,
            191,
            132,
            33,
            147,
            168,
            186,
            52,
            41,
            236,
            123,
            212,
            19,
            81,
            37,
            145,
            33,
            16,
            10,
            225,
            200,
            145,
            35,
            92,
            3,
            217,
            30,
            77,
            31,
            11,
            115,
            219,
            64,
            143,
            178,
            39,
            77,
            173,
            100,
            22,
            146,
            155,
            233,
            234,
            50,
            147,
            47,
            232,
            87,
            189,
            28,
            19,
            23,
            198,
            16,
            215,
            58,
            118,
            147,
            142,
            108,
            136,
            59,
            143,
            0,
            130,
            177,
            4,
            53,
            75,
            159,
            149,
            52,
            94,
            154,
            237,
            8,
            77,
            101,
            169,
            0,
            189,
            185,
            211,
            114,
            177,
            240,
            166,
            159,
            209,
            60,
            207,
            193,
            242,
            223,
            45,
            199,
            121,
            35,
            134,
            35,
            70,
            167,
            38,
            153,
            210,
            103,
            169,
            18,
            226,
            36,
            178,
            80,
            234,
            135,
            228,
            73,
            144,
            246,
            75,
            181,
            53,
            179,
            210,
            68,
            145,
            42,
            146,
            20,
            20,
            111,
            131,
            21,
            188,
            136,
            213,
            122,
            105,
            243,
            156,
            44,
            40,
            191,
            8,
            12,
            134,
            67,
            230,
            89,
            130,
            178,
            239,
            70,
            213,
            198,
            137,
            56,
            74,
            156,
            209,
            62,
            230,
            107,
            107,
            111,
            167,
            151,
            232,
            115,
            190,
            128,
            83,
            83,
            60,
            44,
            23,
            35,
            169,
            101,
            173,
            165,
            236,
            67,
            164,
            185,
            25,
            45,
            20,
            48,
            183,
            111,
            230,
            11,
            129,
            130,
            143,
            70,
            58,
            192,
            226,
            221,
            220,
            179,
            117,
            118,
            102,
            72,
            20,
            199,
            153,
            163,
            39,
            227,
            41,
            48,
            238,
            16,
            235,
            47,
            82,
            83,
            245,
            73,
            42,
            64,
            13,
            13,
            98,
            213,
            170,
            63,
            97,
            39,
            55,
            248,
            215,
            204,
            157,
            139,
            144,
            95,
            103,
            122,
            146,
            212,
            190,
            0,
            162,
            17,
            31,
            62,
            253,
            236,
            16,
            29,
            167,
            80,
            255,
            35,
            79,
            48,
            90,
            65,
            72,
            160,
            18,
            176,
            102,
            177,
            190,
            56,
            235,
            155,
            151,
            142,
            30,
            232,
            91,
            151,
            180,
            76,
            105,
            214,
            5,
            183,
            166,
            181,
            150,
            216,
            207,
            11,
            90,
            194,
            4,
            93,
            247,
            31,
            60,
            96,
            238,
            237,
            183,
            56,
            189,
            12,
            63,
            21,
            180,
            239,
            203,
            113,
            189,
            145,
            217,
            60,
            184,
            127,
            63,
            133,
            199,
            137,
            67,
            211,
            232,
            163,
            199,
            24,
            165,
            118,
            149,
            104,
            250,
            242,
            92,
            148,
            82,
            153,
            60,
            183,
            3,
            25,
            19,
            52,
            33,
            154,
            154,
            91,
            233,
            96,
            120,
            144,
            78,
            230,
            208,
            196,
            197,
            172,
            105,
            80,
            2,
            94,
            153,
            105,
            106,
            99,
            161,
            144,
            70,
            115,
            11,
            23,
            56,
            165,
            211,
            211,
            44,
            164,
            115,
            200,
            103,
            11,
            200,
            166,
            53,
            209,
            212,
            40,
            13,
            46,
            53,
            178,
            37,
            17,
            69,
            87,
            207,
            17,
            228,
            57,
            110,
            125,
            78,
            210,
            91,
            162,
            1,
            117,
            0,
            73,
            26,
            151,
            102,
            186,
            214,
            57,
            125,
            31,
            83,
            153,
            20,
            73,
            211,
            1,
            164,
            57,
            179,
            156,
            3,
            72,
            198,
            20,
            30,
            3,
            59,
            191,
            217,
            119,
            58,
            46,
            50,
            109,
            65,
            185,
            135,
            69,
            238,
            251,
            232,
            129,
            102,
            203,
            94,
            100,
            210,
            73,
            68,
            57,
            29,
            66,
            44,
            159,
            226,
            188,
            147,
            38,
            135,
            245,
            231,
            33,
            89,
            180,
            66,
            207,
            177,
            160,
            215,
            52,
            220,
            148,
            151,
            75,
            90,
            249,
            66,
            36,
            152,
            121,
            188,
            52,
            127,
            81,
            157,
            18,
            56,
            76,
            178,
            184,
            139,
            247,
            133,
            169,
            89,
            109,
            180,
            233,
            156,
            4,
            217,
            10,
            39,
            132,
            143,
            26,
            89,
            34,
            241,
            62,
            20,
            105,
            34,
            63,
            61,
            124,
            0,
            131,
            135,
            12,
            97,
            121,
            31,
            146,
            236,
            115,
            115,
            37,
            212,
            255,
            200,
            83,
            186,
            6,
            111,
            63,
            72,
            90,
            83,
            40,
            82,
            190,
            232,
            209,
            63,
            145,
            87,
            100,
            25,
            153,
            59,
            213,
            31,
            166,
            57,
            182,
            71,
            255,
            124,
            230,
            45,
            10,
            39,
            193,
            9,
            221,
            59,
            90,
            159,
            202,
            59,
            94,
            40,
            157,
            15,
            154,
            178,
            164,
            124,
            247,
            96,
            140,
            123,
            53,
            58,
            60,
            20,
            112,
            145,
            147,
            172,
            24,
            140,
            59,
            99,
            200,
            39,
            73,
            16,
            29,
            35,
            127,
            144,
            142,
            77,
            137,
            166,
            80,
            95,
            224,
            99,
            230,
            117,
            155,
            222,
            83,
            202,
            105,
            205,
            101,
            187,
            208,
            20,
            215,
            36,
            149,
            165,
            9,
            160,
            39,
            153,
            129,
            191,
            68,
            115,
            28,
            167,
            149,
            73,
            85,
            56,
            126,
            15,
            175,
            89,
            78,
            139,
            28,
            226,
            212,
            188,
            100,
            46,
            137,
            12,
            235,
            106,
            139,
            15,
            130,
            143,
            123,
            203,
            126,
            71,
            94,
            95,
            195,
            33,
            192,
            193,
            137,
            68,
            157,
            57,
            56,
            66,
            10,
            85,
            102,
            216,
            25,
            163,
            215,
            252,
            33,
            86,
            209,
            234,
            88,
            12,
            251,
            108,
            242,
            176,
            205,
            222,
            182,
            232,
            109,
            218,
            73,
            160,
            58,
            224,
            81,
            62,
            37,
            50,
            146,
            38,
            210,
            122,
            184,
            182,
            94,
            103,
            155,
            226,
            132,
            163,
            125,
            247,
            194,
            207,
            168,
            163,
            211,
            106,
            128,
            224,
            232,
            86,
            160,
            26,
            241,
            95,
            194,
            10,
            87,
            4,
            212,
            18,
            121,
            252,
            179,
            201,
            83,
            219,
            22,
            201,
            162,
            127,
            106,
            242,
            24,
            144,
            76,
            243,
            215,
            120,
            117,
            85,
            25,
            113,
            40,
            194,
            68,
            170,
            33,
            182,
            154,
            79,
            117,
            87,
            201,
            85,
            125,
            250,
            190,
            59,
            224,
            200,
            251,
            127,
            130,
            75,
            94,
            3,
            195,
            37,
            175,
            129,
            225,
            146,
            215,
            192,
            112,
            201,
            107,
            96,
            184,
            228,
            53,
            48,
            92,
            242,
            26,
            24,
            46,
            121,
            13,
            12,
            151,
            188,
            6,
            134,
            75,
            94,
            3,
            195,
            37,
            175,
            129,
            225,
            146,
            215,
            192,
            112,
            201,
            107,
            96,
            184,
            228,
            53,
            48,
            250,
            140,
            60,
            125,
            187,
            211,
            55,
            61,
            65,
            231,
            68,
            244,
            172,
            47,
            228,
            46,
            234,
            135,
            186,
            147,
            103,
            9,
            19,
            236,
            87,
            110,
            251,
            147,
            92,
            29,
            36,
            114,
            81,
            63,
            212,
            157,
            60,
            29,
            97,
            176,
            176,
            95,
            205,
            117,
            14,
            69,
            135,
            134,
            236,
            95,
            59,
            112,
            81,
            31,
            212,
            253,
            24,
            68,
            45,
            172,
            22,
            234,
            24,
            68,
            237,
            31,
            197,
            113,
            81,
            31,
            244,
            201,
            25,
            22,
            161,
            246,
            96,
            144,
            52,
            78,
            166,
            211,
            69,
            125,
            209,
            39,
            228,
            73,
            227,
            106,
            205,
            167,
            139,
            190,
            65,
            159,
            152,
            205,
            218,
            147,
            99,
            22,
            197,
            162,
            126,
            88,
            239,
            252,
            193,
            26,
            23,
            245,
            65,
            159,
            145,
            39,
            179,
            89,
            123,
            4,
            208,
            146,
            231,
            162,
            94,
            0,
            254,
            3,
            72,
            157,
            255,
            99,
            145,
            151,
            4,
            124,
            0,
            0,
            0,
            0,
            73,
            69,
            78,
            68,
            174,
            66,
            96,
            130,
        ]
    )


from urllib.parse import urlparse


class ProxyForwarder:
    server: asyncio.Server = None
    host: str = None
    port: int = None
    scheme: str = None
    fw_host: str = None
    fw_port: int = None
    fw_scheme: str = None

    @property
    def proxy_server(self):
        return self._proxy_server

    def __init__(self, proxy_server):
        self._proxy_server = None

        url = urlparse(proxy_server)
        if not url.scheme:
            # check if ip:port is passed, in which case no forwarder is needed
            if url.path.find(":") != -1:
                self._proxy_server = url.path
        else:
            if not url.username and not url.password:
                # if no username and password are provided in the proxy url,
                # we are not needed either
                self.scheme = url.scheme
                self._proxy_server = url.geturl()
            else:
                self.port = free_port()
                self.host = "127.0.0.1"
                self.scheme = url.scheme
                self.fw_port = url.port
                self.fw_host = url.hostname
                self.fw_scheme = url.scheme
                self.username = url.username
                self.password = url.password
                # report back ourselves as the proxy server
                self._proxy_server = f"{self.scheme}://{self.host}:{self.port}"

                logger.info(
                    "socks proxy with authentication is requested : %s" % proxy_server
                )
                logger.info("starting forward proxy on %s:%d" % (self.host, self.port))
                logger.info("which forwards to %s" % proxy_server)
                asyncio.ensure_future(self.listen())

    async def listen(self):
        self.server = await asyncio.start_server(
            self.handle_request, host=self.host, port=self.port
        )
        await self.server.start_serving()

    async def handle_request(
        self, reader: asyncio.StreamReader, writer: asyncio.StreamWriter
    ):
        if self.scheme.startswith("socks"):
            return await self.handle_socks_request(reader, writer)

    async def handle_socks_request(
        self, reader: asyncio.StreamReader, writer: asyncio.StreamWriter
    ):
        import socket
        from struct import calcsize, pack, unpack

        NO_ADDR = "0.0.0.0"
        ATYP_IPv4 = 0x01
        ATYP_DNS = 0x03
        ATYP_IPv6 = 0x04

        # import aiosocks2
        async def read(fmt):
            """
            Read from the byte stream
            :param str fmt: struct format specifier
            :return tuple:
            """
            data = await reader.read(calcsize(fmt))
            return unpack(fmt, data)

        version, num_methods = await read(">BB")
        methods = await read("!" + "B" * num_methods)

        # signal to the client there is no username, password required
        # meanwhile, we do need auth to the upstream server
        writer.write(pack("!BB", version, 0))

        # read command from the client
        version, cmd, resv, atyp = await read(">BBBB")

        if atyp == ATYP_IPv4:
            ip_packed = await reader.read(4)
            port = (await read("!H"))[0]
            ip_addr = socket.inet_ntop(socket.AF_INET, ip_packed)
            hostname = None
        elif atyp == ATYP_IPv6:
            ip_packed = await reader.read(16)
            port = (await read("!H"))[0]
            ip_addr = socket.inet_ntop(socket.AF_INET6, ip_packed)
            hostname = None
        elif atyp == ATYP_DNS:
            hostname_len = (await read("!B"))[0]
            hostname = (await read("!{}s".format(hostname_len)))[0]
            port = (await read("!H"))[0]
            ip_addr = None

        if hostname:  # noqa
            if not ip_addr:  # noqa
                ip_addr = socket.gethostbyname(hostname)  # noqa
        else:
            hostname = socket.gethostbyaddr(ip_addr)  # noqa

        # connect to the upstream proxy
        remote_reader, remote_writer = await asyncio.open_connection(
            host=self.fw_host, port=self.fw_port
        )

        # handshake with upstream proxy
        remote_writer.write(pack(">BBB", version, 1, 2))
        server_version, server_auth_method = await remote_reader.read(calcsize(">BB"))

        #  authenticate to upstream proxy
        if server_auth_method == 2:
            auth_ticket = pack(
                f">BB{len(self.username)}sB{len(self.password)}s",
                1,
                len(self.username),
                self.username.encode(),
                len(self.password),
                self.password.encode(),
            )

            remote_writer.write(auth_ticket)
            await remote_writer.drain()
            ver, result = await remote_reader.read(calcsize("!BB"))

            if result != 0:
                raise Exception("socks authentication error: %s" % result)

        # forward client socks5 message to upstream proxy
        remote_writer.write(pack(">BBBB", version, cmd, resv, atyp))
        remote_writer.write(pack(">B", hostname_len))
        remote_writer.write(pack(f"!{hostname_len}s", hostname))
        remote_writer.write(pack("!H", port))

        # create a tunnel between client and upstream proxy
        event = asyncio.Event()
        tasks = self.pipe(remote_reader, writer, event), self.pipe(
            reader, remote_writer, event
        )
        await asyncio.gather(*tasks)

    @staticmethod
    async def pipe(
        reader: asyncio.StreamReader, writer: asyncio.StreamWriter, event: asyncio.Event
    ):
        logger.debug("client proxy to authenticated proxy pipe")
        while not event.is_set():
            try:
                data = await asyncio.wait_for(reader.read(2**16), 1)
                if not data:
                    break
                # simply forward

                writer.write(data)
            except asyncio.TimeoutError:
                continue
        event.set()
